#include "DynamicPlanning.h"

int DynamicPlanning::ClimbStairsDP(int n) {
    if (n == 1 || n == 2) {
        return n;
    }
    std::vector<int> dp(n + 1,0);
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3;i < n + 1;i++) {
        dp[i] = dp[i -1] + dp[i - 2];
    }
    return dp[n];
}

int DynamicPlanning::ClimbStairsDPComp(int n) {
    if (n == 1 || n == 2) {
        return n;
    }
    int a = 1;
    int b = 2;
    int temp = 0;
    for(int i = 3;i < n + 1;i++) {
        temp = b;
        b = a + b;
        a = temp;
    }
    return b;
}

int DynamicPlanning::minCostClimbStairsDP(std::vector<int>& cost) {
    int n = cost.size() - 1;
    if(n == 1 || n == 2) {
        return cost[n];
    }
    std::vector<int> dp(n + 1,0);
    dp[1] = cost[1];
    dp[2] = cost[2];
    for(int i = 3;i < n + 1;i++) {
        dp[i] = std::min(dp[i-1],dp[i- 2]) + cost[i];
    }
    return dp[n];
}

int DynamicPlanning::minPathSumDFS(std::vector<std::vector<int>>& grid,int i,int j) {
    // 若递归到左上角单元格，则终止搜索
    if(i == 0 && j == 0) {
        return grid[0][0];
    }
    // 如果行列索引月结，返回正无穷代价
    if(i <0 || j < 0) {
        return INT32_MAX;
    }
    // 递归计算从左上角到(i-1,j)和(i,j-1)的最小路径代价
    int up = minPathSumDFS(grid,i - 1,j);
    int left = minPathSumDFS(grid,i,j - 1);
    return std::min(up,left) != INT32_MAX ? std::min(up,left) + grid[i][j] : INT32_MAX;
}

//引入和网格grid相同尺寸的记忆列表mem,用于记录各个子问题的解，并将重叠子问题进行剪枝
int DynamicPlanning::minPathSumDFSMem(std::vector<std::vector<int>>& grid,std::vector<std::vector<int>>& mem,int i,int j) {
    // 若递归到左上角单元格，则终止搜索
    if(i == 0 && j == 0) {
        return grid[0][0];
    }
    // 如果行列索引越界，返回正无穷代价
    if(i <0 || j < 0) {
        return INT32_MAX;
    }
    // 如果已有记录，则直接返回
    if(mem[i][j] != -1) {
        return mem[i][j];
    }
    // 递归计算从左上角到(i-1,j)和(i,j-1)的最小路径代价
    int up = minPathSumDFS(grid,i - 1,j);
    int left = minPathSumDFS(grid,i,j - 1);
    mem[i][j] = std::min(up,left) != INT32_MAX ? std::min(up,left) + grid[i][j] : INT32_MAX;
    return mem[i][j];
}

    // 最小路径和-动态规划
int DynamicPlanning::minPathSumDP(std::vector<std::vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();
    // 初始化dp表
    std::vector<std::vector<int>> dp(n,std::vector<int>(m));
    dp[0][0] = grid[0][0];
    // 状态转移，首行
    for(int j = 1;j < m;j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    // 状态转移，首列
    for(int i = 1;i < n;i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    // 状态转移，其他行列
    for(int i = 1;i < n;i++) {
        for(int j = 1;j < m;j++) {
            dp[i][j] = std::min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[n-1][m-1];
}

int DynamicPlanning::minPathSumDPComp(std::vector<std::vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();
    // 初始化dp表
    std::vector<int> dp(m);
    // 状态转移，首行
    dp[0] = grid[0][0];
    for(int j = 1; j < m;j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // 其余行
    for(int i = 1;i < n;i++) {
        // 首列
        dp[0] = dp[0] + grid[i][0];
        // 其余列
        for(int j = 1;j < m;j++) {
            dp[j] = std::min(dp[j-1],dp[j]) + grid[i][j];
        }
    }
    return dp[m-1];

}

int DynamicPlanning::knapackDFS(std::vector<int> &wgt,std::vector<int>& val,int i,int c) {
    // 如果已选完所有物品或者背包无剩余容量，则返回价值0
    if(i == 0 || c == 0) {
        return 0;
    }
    // 若当前选择的物品重量超过背包剩余容量，则只能不放入背包
    if(wgt[i - 1] > c) {
        return knapackDFS(wgt,val,i - 1,c);
    }
    // 计算不放入和放入物品的最大价值
    int no = knapackDFS(wgt,val,i-1,c);
    int yes = knapackDFS(wgt,val,i-1,c-wgt[i-1]) + val[i-1];
    // 返回两种方案中价值更大的那一个
    return std::max(no,yes);
}


int DynamicPlanning::knapackDFSMem(std::vector<int> &wgt,std::vector<int>& val,std::vector<std::vector<int>>& mem,int i,int c) {
    // 如果已选完所有物品或者背包无剩余容量，则返回价值0
    if(i == 0 || c == 0) {
        return 0;
    }
    // 如果已经有记录，则直接返回
    if(mem[i][c] != -1) {
        return mem[i][c];
    }
    // 若当前选择的物品重量超过背包剩余容量，则只能不放入背包
    if(wgt[i - 1] > c) {
        return knapackDFS(wgt,val,i - 1,c);
    }
    // 计算不放入和放入物品的最大价值
    int no = knapackDFS(wgt,val,i-1,c);
    int yes = knapackDFS(wgt,val,i-1,c-wgt[i-1]) + val[i-1];
    // 返回两种方案中价值更大的那一个
    mem[i][c] = std::max(no,yes);
    return mem[i][c];
}

int DynamicPlanning::knapackDP(std::vector<int> &wgt,std::vector<int>& val,int cap) {
    int n = wgt.size();
    // 初始化dp表
    std::vector<std::vector<int>> dp(n + 1,std::vector<int>(cap + 1,0));
    // 状态转移
    for(int i = 1; i < n + 1;i++) {
        for(int  c = 1;c < cap + 1;c++) {
            // 如果当前物品超过背包容量，只能选择不放物品
            if(wgt[i-1] > c) {
                dp[i][c] = dp[i-1][c];
            }
            else {
                dp[i][c] = std::max(dp[i-1][c],dp[i-1][c-wgt[i-1]] + val[i-1]);
            }
        }
    }
    return dp[n][cap];

}

int DynamicPlanning::knapackDPComp(std::vector<int> &wgt,std::vector<int>& val,int cap) {
    int n = wgt.size();
    // 初始化dp表
    std::vector<int> dp(cap + 1,0);
    // 状态转移
    for(int i = 1;i < n + 1;i++) {
        // 倒序遍历
        for(int c = cap;c >= 0;c--) {
            if(wgt[i-1] <= c) {
                dp[c] = std::max(dp[c],dp[c-wgt[i-1]] + val[i-1]);
            }
        }
    }
    return dp[cap];
}

int DynamicPlanning::unboundedknapackDP(std::vector<int> &wgt,std::vector<int>& val,int cap) {
    int n = wgt.size();
    // 初始化dp表
    std::vector<std::vector<int>> dp(n + 1,std::vector<int>(cap + 1,0));
    for(int i = 1;i < n + 1;i++) {
        for(int c = 1;c < cap + 1;c++) {
            if(wgt[i-1] > c) {
                dp[i][c] = dp[i-1][c];
            }
            else {
                dp[i][c] = std::max(dp[i-1][c],dp[i][c-wgt[i-1]] + val[i-1]);
            }
        }
    }
    return dp[n][cap];
}

int DynamicPlanning::unboundedknapackDPComp(std::vector<int> &wgt,std::vector<int>& val,int cap) {
    int n = wgt.size();
    // 初始化dp表
    std::vector<int> dp(cap + 1,0);
    for(int i = 1;i < n + 1;i++) {
        for(int c = 1;c < cap + 1;c++) {
            if(wgt[i - 1] > c) {
                dp[c] = dp[c];
            }
            else {
                dp[c] = std::max(dp[c],dp[c - wgt[i-1]] + val[i-1]);
            }
        }
    }
    return dp[cap];

}

int DynamicPlanning::CoinsChangeDP(std::vector<int>& coins,int amt) {
    int n = coins.size();
    int MAX = amt + 1;
    // 初始化dp表,dp[i][a]表示前i种面值的硬币组成数值为a的最少硬币数量
    std::vector<std::vector<int>> dp(n + 1,std::vector<int>(amt + 1, 0));
    // 初始化首行
    for(int a = 1;a < amt + 1;a++) {
        dp[0][a] = MAX;
    }
    // 逐行逐列遍历
    for(int i = 1;i < n + 1;i++) {
        for(int a = 1;a < amt + 1;a++) {
            // 如果第i种硬币面值大于a，则不选择硬币i，否则，选与不选取最小
            if(coins[i-1] > a) {
                dp[i][a] = dp[i-1][a];
            }
            else {
                dp[i][a] = std::min(dp[i-1][a],dp[i][a-coins[i-1]] + 1);
            }
        }
    }
    return dp[n][amt] == MAX ? -1 : dp[n][amt];
    
}

int DynamicPlanning::CoinsChangeDPComp(std::vector<int>& coins,int amt) {
    int n = coins.size();
    int MAX = amt + 1;
    // 初始化dp表，省去表示硬币种类的维度,dp[a]表示前i种面值的硬币组成数值为a的最少硬币数量
    std::vector<int> dp(amt + 1,MAX);
    dp[0] = 0;
    for(int i = 1;i < n + 1;i++) {
        for(int a = 1;a < amt + 1;a++) {
            if(coins[i-1] > a) {
                dp[a] = dp[a];
            }
            else {
                dp[a] = std::min(dp[a],dp[a - coins[i-1]] + 1);
            }
        }
    }
    return dp[amt] == MAX ? -1: dp[amt];
}

int DynamicPlanning::CoinsChangeIIDP(std::vector<int>& coins,int amt) {
    int n = coins.size();
    // 初始化dp表，dp[i][a]表示前i种硬币凑出金额a的组合数量
    std::vector<std::vector<int>> dp(n + 1,std::vector<int>(amt + 1,0));
    // 当金额a = 0时，无需硬币即可组成，即只有一种组合数量，所以第一列的值都是1
    for(int i = 0;i < n + 1;i++) {
        dp[i][0] = 1;
    }
    // 其他行、列
    for(int i = 1;i < n + 1;i++) {
        for(int a = 1;a < amt + 1;a++) {
            if(coins[i-1] > a) {
                dp[i][a] = dp[i-1][a];
            }
            else {
                dp[i][a] = dp[i-1][a] + dp[i][a-coins[i-1]];
            }
        }
    }
    return dp[n][amt];
}

int DynamicPlanning::CoinsChangeIIDPComp(std::vector<int>& coins,int amt) {
    int n = coins.size();
    // 初始化dp表，dp[a]表示前i种硬币凑出金额a的组合数量
    std::vector<int> dp(amt + 1,0);
    // 当金额a = 0时，无需硬币即可组成，即只有一种组合数量，所以第一列的值都是1
    dp[0] = 1;
    // 其他行、列
    for(int i = 1;i < n + 1;i++) {
        for(int a = 1;a < amt + 1;a++) {
            if(coins[i-1] > a) {
                dp[a] = dp[a];
            }
            else {
                dp[a] = dp[a] + dp[a-coins[i-1]];
            }
        }
    }
    return dp[amt];
}

int DynamicPlanning::EditDiatance(std::string& s,std::string& t) {
    int n = s.size();
    int m = t.size();
    // 初始化dp表，dp[i][j]表示将s前i个字符变换为t前j个字符的编辑步数
    std::vector<std::vector<int>> dp(n + 1,std::vector<int>(m + 1,0));
    // 首行表示，s为空，t不为空，dp[0][j] = j;
    for(int j = 0;j < m + 1;j++) {
        dp[0][j] = j;
    }
    // 首列表示，s不为空，t为空，dp[i][0] = i;
    for(int i = 0;i < n + 1;i++) {
        dp[i][0] = i;
    }
    // 其余行和列
    for(int i = 1;i < n + 1;i++) {
        for(int j = 1;j < m + 1;j++) {
            // 如果s[i-1]和t[i-1]相同，直接跳过
            if(s[i-1] == t[i-1]) {
                dp[i][j] = dp[i-1][j-1];
            }
            // 最小编辑步数 = 插入、删除、替换三者的最小值+1
            else {
              dp[i][j] = std::min(std::min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]) + 1;
            }
        }
    }
    return dp[n][m];
}

int DynamicPlanning::EditDiatanceComp(std::string& s,std::string& t) {
    int n = s.size();
    int m = t.size();
    // 初始化dp表
    std::vector<int> dp(m + 1,0);
    // 状态转移，首行
    for(int j = 1; j < m + 1;j++) {
        dp[j] = j;
    }
    // 其余行
    for(int i = 1;i < n + 1;i++) {
        // 状态转移，首列
        int leftup = dp[0]; // 暂存dp[i-1][j1]
        dp[0] = i;
        // 其余列
        for(int j = 1;j < m + 1;j++) { 
            int temp = dp[j];
            if(s[i-1] == t[j-1]) {
                dp[j] = leftup;
            }
            else {
                dp[j] = std::min(std::min(dp[j-1],dp[j]),leftup) + 1;
            }
            leftup = temp;  // 更新为下一轮的dp[i-1][j-1]
        }
    }
    return dp[m];
}